package leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

import org.junit.Test;

public class SolveSudoku {

	@Test
	public void testResult() {
		String[] boardStr = new String[] { "..9748...", "7........",
				".2.1.9...", "..7...24.", ".64.1.59.", ".98...3..",
				"...8.3.2.", "........6", "...2759.." };

		char[][] board = new char[9][9];

		for (int i = 0; i < 9; i++) {
			board[i] = boardStr[i].toCharArray();
		}

		SolveSudoku ss = new SolveSudoku();

		ss.solveSudoku(board);

		for (int i = 0; i < 9; i++) {
			System.out.println(Arrays.toString(board[i]));
		}

	}

	public void solveSudoku(char[][] board) {
		solve(board);
	}

	private boolean solve(char[][] board) {
		int p = findPos(board);
		if (p == -1)
			return true;
		else {
			int r = p / 9;
			int c = p % 9;

			List<Integer> fits = findFit(board, r, c);

			if (fits.size() == 0)
				return false;

			for (Integer f : fits) {
				board[r][c] = (char) (f + '0');
				if (solve(board))
					return true;
			}

			board[r][c] = '.';
			return false;
		}
	}

	public int findPos(char[][] board) {
		for (int r = 0; r < board.length; ++r) {
			for (int c = 0; c < board[0].length; ++c) {
				if (board[r][c] == '.')
					return r * 9 + c;
			}
		}

		return -1;
	}

	public List<Integer> findFit(char[][] board, int r, int c) {
		boolean[] fits = new boolean[9];
		for (int i = 0; i < fits.length; ++i) {
			fits[i] = true;
		}

		for (int i = 0; i < 9; ++i) {
			if (board[i][c] != '.')
				fits[(int)(board[i][c]-'0')-1] = false;
			if (board[r][i] != '.')
				fits[(int)(board[r][i]-'0')-1] = false;
		}

		int cr = (r < 3) ? 0 : (r < 6) ? 3 : 6;
		int cc = (c < 3) ? 0 : (c < 6) ? 3 : 6;

		for (int i=0; i < 3; ++i) {
			for (int j=0; j < 3; ++j) {
				if (board[cr+i][cc+j] != '.')
					fits[(int)(board[cr+i][cc+j]-'0')-1] = false;
			}
		}

		List<Integer> res = new ArrayList<Integer>();
		for (int i = 0; i < fits.length; ++i) {
			if (fits[i])
				res.add(i+1);
		}

		return res;
	}
}
